package top.lcm668.study.oj.base.sortmethods;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 17:40
 * 桶排序,为了验证方便
 */
public class BucketSort<T extends Comparable<T>> extends BaseSort<T> {

    /**
     * ToDO: 运行 bug
     * @see https://blog.csdn.net/MobiusStrip/article/details/83785159?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163317853816780261974272%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163317853816780261974272&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-9-83785159.first_rank_v2_pc_rank_v29&utm_term=%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187
     * @param arr
     * @param isAsc 默认升序排列
     */
    @Override
    protected void sort(T[] arr, boolean isAsc) {
        List<Integer> nums = Arrays.asList((Integer[]) arr);
        arr = (T[]) bucketSort(nums, 3).toArray();
    }

    private ArrayList<Integer> bucketSort(List<Integer> arr, int bucketSize) {
        if (arr == null || arr.size() < 2) {
            return (ArrayList<Integer>) arr;
        }
        int max = arr.get(0), min = arr.get(0);
        // 找两端的最值
        for (int i = 0; i < arr.size(); i++) {
            max = Math.max(max, arr.get(i));
            min = Math.min(min, arr.get(i));
        }

        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < arr.size(); i++) {
            bucketArr.get(arr.get(i) - min / bucketSize).add(arr.get(i));
        }

        for (int i = 0; i < bucketCount; i++) {
            // 如果带排序数组中有重复数字时
            if (bucketSize == 1) {
                for (int i1 = 0; i1 < bucketArr.get(i).size(); i1++) {
                    resultArr.add(bucketArr.get(i).get(i1));
                }
            } else {
                if (bucketCount == 1) {
                    bucketSize--;
                }
                ArrayList<Integer> temp = bucketSort(bucketArr.get(i), bucketSize);
                for (int i1 = 0; i1 < temp.size(); i1++) {
                    resultArr.add(temp.get(i1));
                }
            }
        }
        return resultArr;
    }
}
